package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.Stack;

/**
 * @author lixqw
 * @date 2020/8/21
 */
public class MinimumDistanceBetweenBSTNodes783 {

    static class Solution {
        public int minDiffInBST(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode pre = null;
            int dlt = 0x7fffffff;
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (pre != null) {
                    dlt = Math.min((root.val - pre.val), dlt);
                }
                if (dlt == 1) return 1;
                pre = root;
                root = root.right;
            }
            return dlt;
        }
    }

    static class Solution2 {
        int dlt = 0x7fffffff;
        TreeNode pre = null;
        public int minDiffInBST(TreeNode root) {
            if (root == null || dlt == 1) {
                return dlt;
            }
            minDiffInBST(root.left);
            if (pre != null) {
                dlt = Math.min(root.val - pre.val, dlt);
            }
            pre = root;
            minDiffInBST(root.right);
            return dlt;
        }
    }

    
}
